package com.note.feng.leetcode.algorithms.easy.ten;

public class ThousandSeventyOne {
    /**
     * 1071 字符串的最大公因子
     * 对于字符串 s 和 t，只有在 s = t + ... + t（t 自身连接 1 次或多次）时，我们才认定 “t 能除尽 s”。
     *
     * 给定两个字符串 str1 和 str2 。返回 最长字符串 x，要求满足 x 能除尽 str1 且 X 能除尽 str2 。
     *
     * 示例 1：
     *
     * 输入：str1 = "ABCABC", str2 = "ABC"
     * 输出："ABC"
     * 示例 2：
     *
     * 输入：str1 = "ABABAB", str2 = "ABAB"
     * 输出："AB"
     * 示例 3：
     *
     * 输入：str1 = "LEET", str2 = "CODE"
     * 输出：""
     *
     * 提示：
     *
     * 1 <= str1.length, str2.length <= 1000
     * str1 和 str2 由大写英文字母组成
     *
     * 来源：力扣（LeetCode）
     * 链接：https://leetcode.cn/problems/greatest-common-divisor-of-strings
     */
    /**
     * 解法：枚举
     * 计算出两个字符串长度的所有公约数，从大到小遍历，直到第一次满足题意为止
     * @param str1
     * @param str2
     * @return
     */
    public String gcdOfStrings(String str1, String str2) {
        int len1 = str1.length(), len2 = str2.length();
        int len = Math.min(len1, len2);
        for (int i = len; i > 0; i--) {
            if(len1 % i == 0 && len2 % i == 0){
                String str = str1.substring(0, i);
                if(check(str, str1) && check(str, str2)){
                    return str;
                }
            }
        }
        return "";
    }

    private Boolean check(String str, String s){
        int count = s.length() / str.length() - 1;
        String t = str;
        for (int i = 0; i < count; i++) {
            t += str;
        }
        return t.equals(s);
    }

}
